﻿#include<iostream>
#include<map>
using namespace std;



class Solution 
{
public:
	Node* copyRandomList(Node* head) {
		map<Node*, Node*> nodeMap;
		Node* copyhead = nullptr, * copytail = nullptr;
		Node* cur = head;
		while (cur)
		{
			if (copytail == nullptr)
			{
				copyhead = copytail = new Node(cur->val);
			}
			else
			{
				copytail->next = new Node(cur->val);
				copytail = copytail->next;
			}

			// 原节点和拷⻉节点map kv存储 
			nodeMap[cur] = copytail;
			cur = cur->next;
		}
		// 处理random 
		cur = head;
		Node* copy = copyhead;
		while (cur)
		{
			if (cur->random == nullptr)
			{
				copy->random = nullptr;
			}
			else
			{
				copy->random = nodeMap[cur->random];
			}
			cur = cur->next;
			 copy = copy->next;
		}
		return copyhead;
	}
};
